package mo.tags.dp;

import java.util.Arrays;

public class L45 {

    public int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, len-1);
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            int steps = nums[i];
            for (int j = 0; j <= steps && i+j<len; j++) {
                dp[i+j] = Math.min(dp[i+j], dp[i]+1);
            }
        }
        return dp[len-1];
    }

}
